In recent years, there has been a dramatic increase in the need for systems that can protect digital data from potential eavesdroppers, forgers, and other adversaries. This is largely due to the fact that an unprecedented portion of all commercial transactions and communications are now handled with digital electronics. In addition, the sophistication of potential adversaries has increased, which has made the problem of protecting digital data even more pressing.
In response to this need, a wide variety of interesting and novel schemes have been developed for protecting and authenticating digital data. The problem now faced by many corporations and government bodies is to choose a scheme from among the many that will be both secure and economical. NIST, in particular, is faced with the task of selecting "standard" methods for encrypting and authenticating data.
Traditionally, written data has been authenticated by appending the handwritten signature of the appropriate individual to the data. Modern methods for authenticating digital data proceed in a similar fashion except that the handwritten signature is replaced with a digital signature. The digital signature consists of a stream of bits which is computed by the signer based on the message being signed. The digital signature should have the properties that anyone can verify that a signature is the valid signature of the signer for the associated message, and that only the signer is able to generate the signature.
The most popular method for computing digital signatures today is the RSA scheme. In the RSA scheme, each individual is provided with a secret pair of large (e.g., 500-digit) prime numbers P.sub.1 and P.sub.2. The pair (P.sub.1,P.sub.2) is referred to as the secret key for the individual. The corresponding public key for the individual is the pair (Q,r) where Q=P.sub.1 P.sub.2 and r is a fixed positive integer that is relatively prime to P.sub.1 -1 and P.sub.2 -1. The signature for a message M is a number x for which x.sup.r =h(M)mod Q. The function h is a publicly-available hash function that maps any data string M into a k-bit number where k.ltoreq.log Q. The step of computing h(M) is known as pre-hashing. This initial step is common to all known digital signature algorithms because applying the signing procedure directly to M, rather than h(M), is either impossible or impossibly time-consuming. The hash function h used for pre-hashing needs to have two important properties: it must be easy to compute h(M) given M but impossibly hard to compute M given h(M), and it should be impossibly hard to find two strings M and M' such that h(M)=h(M').
Many similar schemes have also been proposed, including the well-known DSA algorithm. The practicality of schemes such as RSA and DSA is based on several factors: it is not overly difficult for an individual's computer to produce a signature x for a message M given that the computer knows the secret key (P.sub.1, P.sub.2), the fact that it is relatively easy for someone else's computer to verify that x is a signature for M given knowledge of the public key (r,M), the fact that the signature itself is relatively short (e.g., it consists of about 1000 bits), and the fact that the public key is also relatively short (e.g., it also consists of about 1000 bits).
The security of schemes such as RSA and DSA is based on the hope that it is impossible for an adversary to produce a signature for any message M without knowledge of the private key, even if the adversary is aware of the public key and can obtain valid signatures for messages other than M. More specifically, the security of these prior art schemes is based on the hope that number-theoretic problems such as factoring and computing discrete logarithms are impossibly hard for almost all large numbers, the hope that it is impossibly hard to find a collision for the hash function (i.e., to find a pair of messages M and M' such that h(M)=h(M')) and that it is impossibly hard to invert the hash function (i.e., to compute an M such that h(M)=z given z), and the hope that an adversary must perform one of the preceding (presumably difficult) tasks in order to be able to forge a signature.
For example, if the adversary is able to factor, then he can compute the private key from the public key, whereupon he can begin to forge signatures at will for the RSA scheme. If the adversary can compute discrete logarithms, then he can compute forged signatures for the DSA scheme directly, without knowledge of the secret key. Moreover, if the adversary can find two messages M and M' for which h(M)=h(M'), then he can forge a signature for M' by obtaining a legitimate signature for M (since the signatures for M and M' are the same). If the adversary can invert h, then he can forge signatures by an alternative method using a slightly more complex attack. Finally, it might be possible for an adversary to forge signatures using an altogether different as-yet-unknown attack. Hence, in addition to the hope that it is not possible to achieve a known attack, the security of schemes such as RSA depend on the hope that there are no easier alternative attacks. In summary, this means that the security of signature schemes such as RSA and DSA is based on assumptions which may not always be defensible.
It is also known in the prior art how to convert a hash function into a 1-time signature scheme, i.e., a signature that is used with one particular message and then discarded. If the hash function is ideal (or at least secure against inversion), then the signature scheme will be secure against forgery. In one known technique, the Basic Lamport Scheme, there are two important parameters: k and m. The value of m denotes the length of the message to be signed and it must be specified in advance. The parameter k is the security parameter and h is a hash function with k-bit outputs. The secret signing key Ks consists of 2 m randomly-generated strings A.sub.1, . . . ,A.sub.m, B.sub.1, . . . ,B.sub.m, each with k bits. The corresponding public verification key Kp consists of X.sub.1, . . . ,X.sub.m, Y.sub.1, . . . ,Y.sub.m, where X.sub.i =h(A.sub.i) and Y.sub.i =h(B.sub.i) for 1.ltoreq.i.ltoreq.m. The signature of an m-bit message M=b.sub.1 . . . b.sub.m consists of S.sub.1, S.sub.2, . . . ,S.sub.m where S.sub.i =A.sub.i (if b.sub.i =0) and B.sub.i (if b.sub.i =1). The signature is verified by checking that h(S.sub.i)=X.sub.i (if b.sub.i =0) and Y.sub.i (if b.sub.i =1).
The Basic Lamport Scheme has been improved in various ways. One improvement, the Lamport/2 Scheme, essentially halves all the costs of the basic scheme. In the Lamport/2 scheme, the signer chooses the secret key by selecting at random m+n+2 k-bit strings A.sub.1, . . . ,A.sub.m, B.sub.1, . . . ,B.sub.n, C.sub.0, C.sub.1, where n=[log ([m/2]+1)]. The signer then sets the corresponding public key to consist of the values X.sub.i =h(A.sub.i) for 1.ltoreq.i.ltoreq.m, Y.sub.j =h(B.sub.j) for 1.ltoreq.i.ltoreq.n, and Z.sub.d =h(C.sub.d) for d=0,1. The signature of an m-bit message M=b.sub.l . . . b.sub.m is computed as follows. If more than m/2 of the m bits of M are zeros, then the signer complements all of the bits of M and sets d=1. Otherwise, the b.sub.i are left unchanged and d is set to 0. The signer next computes the number e of zeros among the b.sub.i 's. Since by definition, 0.ltoreq.e.ltoreq.m/2, the binary representation of e is e.sub.l . . . e.sub.n. If .epsilon. denotes the empty string, the signature of M then consists of S.sub.1, . . . ,S.sub.m, T.sub.1, . . . ,T.sub.n, U where S.sub.i =A.sub.i (if b.sub.i =0) and .epsilon. otherwise for 1.ltoreq.i.ltoreq.m, and T.sub.j =B.sub.j (if .epsilon..sub.j =0) and .epsilon. otherwise for 1.ltoreq.j.ltoreq.n, and U=C.sub.d. The signature of M is verified by first computing d from U and the two Z-values in the public key, and then checking that each of the appropriate preimages of h has been correctly supplied in the signature.
The main drawback of the 1-time schemes described above is that they can only be used to sign a single message. To overcome this disadvantage, it is also known in the prior art how to convert a 1-time scheme into an N-time scheme, where N is an arbitrarily large parameter that is selected in advance. In one trivial technique, any of the 1-time schemes described above can be converted into an N-time scheme by simply forming a set of N secret and public keys and using each set once. The public (and secret) key for the N-time scheme will then be the union (or concatenation) of the individual 1-time keys.
Unfortunately, there are two serious problems with this approach. First, the public and secret key are enormous. For example, even if N=1000, the public key will consist of millions of bits, which is clearly not practical for most applications. Second, the scheme is vulnerable to attack since the adversary only has to find the preimage of one of the strings in one of the 1-time keys in order to forge a signature. As the number of targets increases, the security of the overall N-time scheme decreases substantially.
One technique for overcoming the difficulties with key length in the trivial N-time scheme is the so-called Basic Merkle Scheme. In this scheme, the signer starts by setting up N 1-time schemes using a common hash function h. Let K.sub.s.sup.(i) denote the secret key of the ith 1-time scheme and let K.sub.p.sup.(i) denote the public key of the ith 1-time scheme for 1.ltoreq.i.ltoreq.N. Then the secret key of the N-time scheme will be K.sub.s =K.sub.s.sup.(1), . . . ,K.sub.s.sup.(N). The public key of the N-time scheme is obtained using a tree-based hashing procedure. In particular, let tn denote the complete binary tree with N leaves, and label the nodes of .tau.n so that v.sub..phi. is the root (where .phi. denotes the empty string), v.sub.0 and v.sub.1 are the left and right children of v.sub..phi., respectively, and so that v.sub..alpha.0 and v.sub..alpha.1 are the left and right children of v.sub..alpha., respectively, for all .alpha. belonging to [0,1].sup.i where i&lt;log N. Each node in the tree has a special memory location that contains a k-bit hash value. The value stored in node v.sub..alpha. is R.sub..alpha. for all .alpha. (0.ltoreq.(.alpha.).ltoreq.log N). The value stored in the jth leaf v.sub.bin (.sub.j) is R.sub.bin (.sub.j)=h(K.sub.p (.sup.j)) for 0.ltoreq.j&lt;N, where bin(j) denotes the log N-bit binary representation of j and h is a hash function with k-bit outputs. The values stored in the interior nodes of the tree are computed in a bottom-up fashion as follows. The value stored in node v.sub..alpha. is R.sub..alpha. =h(R.sub..alpha.0 R.sub..alpha.) for all .alpha. (0.ltoreq.(.alpha.).ltoreq.log N). The k-bit value R.sub..phi. that is computed and stored at the root serves as the public key Kp for the N-time scheme.
In the Basic Merkle Scheme the signature for a message M is formed as follows. Let i denote the number of signatures performed previously by the owner of the tree .tau..sub.N (for 0.ltoreq.i&lt;N) and let b.sub.1 b.sub.2 . . . blogN denote the log N-bit binary representation of i. In addition, define .alpha..sub.j =b.sub.1 b.sub.2 . . . b.sub.j-1 b.sub.j for 1.ltoreq.j.ltoreq.log N. Then the signature for M consists of the signature for M produced by the ith 1-time scheme (counting starting with i=0) along with i, the public key K.sub.p (.sup.i) of the ith 1-time scheme, and R.sub..alpha.j 1.ltoreq.j.ltoreq.log N. Given i, K.sub.p (.sup.i), and R.sub..alpha.j 1.ltoreq.j.ltoreq.log N, it is easy for the verifier to check that the signature is authentic. First, the verifier checks that the portion of the signature for the ith one-time scheme is valid assuming that the declared value of K.sub.p (.sup.i ) is indeed the public key for the ith one-time scheme. Next, the verifier checks that K.sub.p (.sup.i) is authentic by computing Ralpha for all alpha that are prefixes of bin(i). These are the values contained in nodes that are on the path from leaf i to the root in .tau..sub.N. If the value for R.phi. computed by the verifier matches the public key for the tree, then the signature is authentic.
Although the Basic Merkle Scheme has a short public key and short signatures, it has a very large secret key and thus it requires the signer to remember a large amount of data (N secret 1-time keys, N public 1-time keys, and the 2.sup.N-1 R-values of .tau..sub.N). The memory requirements of the Basic Merkle Scheme are likely prohibitive for many applications. One solution to the memory problem is to generate all the N 1-time keys from a single and short private key, which serves as the seed for a random number generator, and then reconstruct the entire tree .tau..sub.N prior to signing each message. Although this approach solves the memory problem, it requires a considerable amount of time to produce each signature. Another solution, the Small-Memory Merkle Scheme, requires the signer to remember (log.sup.2 N)/2 R-values from the tree and log N states of the pseudo-random number generator at any time. In addition, the method can generate a signature by regenerating log N secret and public 1-time keys and by performing log N additional hash computations.
The major problem with both the Basic Merkle Scheme and the Small-Memory Merkle Scheme is security. In particular, the schemes are vulnerable to numerous square-root attacks, several of which are described in what follows. As a consequence, a signer using one of these schemes will need to use values of k and m that are at least twice as large as the values that would be needed for any 1-time scheme in isolation. This means that key lengths, signature lengths, signing times, memory requirements, and verifying times will all need to be increased by an order of magnitude in an attempt to make up for these insecurities.
The best known of these attacks is the attack on the pre-hashing. This is a chosen-message attack aimed at the messages to be signed. It works whenever the digital signature of a long message M is obtained by first hashing the message and then properly signing h(M). In this attack, the enemy chooses 2.sup.m/2 messages M.sub.i and then computes the m-bit values h(M.sub.i) which will be actually signed. By the birthday paradox, with constant probability he finds i and j such that h(M.sub.i)=h(M.sub.j). Then, by requesting and obtaining the signature of M.sub.i from the signer, the enemy forges the signature of M.sub.j. Hence Merkle's algorithm and all previously known signing algorithms are at most 2.sup.m/2 secure (as defined herein, this measure of security means that a signature can be forged with reasonable probability by an algorithm running in 2.sup.m/2 steps), even if h is an ideal hash function.
It should be appreciated that in such a forgery the enemy may essentially choose the message whose signature is forged. For example, the forger may compute a set 2.sup.m/2 h-hashed "innocent" messages (i.e., requests for very small payments), a set of 2.sup.m/2 h-hashed "advantageous" messages (i.e., requests for very large payments), and then look for a point in the intersection of these two sets. Then, by obtaining a signature for a single small check, the forger will be able to forge the signature of a large check. This weakness forces all prior digital signature schems to use a large value of m.
Another form of attack of the Merkle Scheme is the tree attack which works regardless of the 1-time signature scheme employed at the leaves and regardless of what pseudo-random number generator is used to generate 1-time secret keys. The first attack is a collision-based attack aimed at the leaves of the tree. Leaf i stores the k-bit value R.sub.bin(i) =h(K.sub.p.sup.(i)), which is authenticated via the sequence of R-values comprising the ith authenticating path. In this attack, the enemy tries to compute a 1-time public key K.sub.p for which he knows the corresponding secret key and for which h(K.sub.p)=h(K.sub.p.sup.(i)) for some small i. Then, he can use one of the authenticating paths (namely the ith path) that has already been released by the legitimate signer to forge an authentication of K.sub.p. If the signer has signed 2.sup.k/2 messages, then 2.sup.k/2 leaf values have become available to the enemy. The enemy then generates 2.sup.k/2 1-time public keys, K.sub.p.sup.(1) ', . . . ,K.sub.p.sup.(2k/2) ' , together with their corresponding secret keys, and hashes them to k-bit values by using h. By the birthday paradox, with constant probability, he finds an a and b such that 1.ltoreq.a,b.ltoreq.2.sup.k/2 and h(K.sub.p.sup.(a))=h(K.sub.p.sup.(b) '). In this case, the legitimate ath authenticating path also authenticates K.sub.p.sup.(b) ', and since the enemy knows K.sub.s.sup.(b) ', he can then forge the signature of any message he wants. Thus in this attack, the enemy pretends that the forged signature is that of the ith message, since the current total number of messages legitimately signed is not generally available to the verifier.
Thus, the Merkle Scheme is at most 2.sup.k/2 -secure, even if h is an ideal hash function. Moreover, the attack can also be applied to the internal nodes of the signing tree. Once 2.sup.k/2 R-values have been revealed on any level of the tree (or in any collection of trees), the enemy can mount a collision-based attack by generating a tree of his own choosing and hoping to match an R-value on the same level of the tree. The attack can also be extended for use with many signers. Thus even if the Merkle scheme were made secure for a single signer, problems can arise when there are many signers. In particular, once a total of 2.sup.k/2 messages have been signed, a collision-based attack can proceed as before.
Thus, the N-time Merkle Scheme is generally described given an "abstract but secure" 1-time signature scheme. As noted above, however, no matter what the 1-time signature scheme may be, the Merkle schemes are prone to attacks. Depending on the 1-time signature scheme that is used, however, there may also be additional attacks. For example, depending on the 1-time scheme used, then it is also possible to apply a collision attack aimed at the individual hashes in the 1-time public key. In particular, once a total of 2.sup.k/2 hash values have been revealed (and m or more are revealed for each signature), then the attacker can apply a collision-based attack to find a preimage of one of the hashes in one of the 1-time public keys in about 2.sup.k/2 steps. Once a preimage is found, then the attacker can forge a signature by using a chosen-message attack. Hence, the forger can expect to be able to produce a forgery in about 2.sup.k/2 steps.
There are also attacks on the Small-Memory Merkle Scheme aimed at the pseudo-random number generator. Even if the pseudo-random number generator is unpredictable, if it is used in a standard way, a collision-based attack can be used to invert the generator.
To overcome some of these significant problems, Merkle has proposed an Alternative Merkle Scheme in which each node contains a 1-time scheme that is used to authenticate the 1-time schemes in its left and right children. The public key of the scheme is the same as the public key of the 1-time scheme in the root of the tree. This scheme has the advantage that the value of N does not need to be fixed in advance, but has the greater disadvantage that the signatures become very large as N increases, which makes the scheme impractical for even moderate values of N. The scheme also has security problems that are analogous to those described above.
As a result of the current state of the prior art, there remains a long felt need for provably fast and secure digital signature algorithms based on secure hash functions.